package com.hmdp.whd;

class Trie {
    // 前缀树根节点不存放数据
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode preNode = root;
        for (int i = 0; i < word.length(); i++) {
            int ch = word.charAt(i) - 'a';
            // 当前字母不在树中,新增节点
            if(preNode.next[ch] == null){
                preNode.next[ch] = new TrieNode();
            }
            preNode = preNode.next[ch];
        }
        // 遍历完后preNode在字母结束位置,标记
        preNode.word = word;
    }

    public boolean search(String word) {
        TrieNode preNode = startWithNode(word);
        return preNode!=null && preNode.word!=null;
    }

    public boolean startsWith(String prefix) {
        return startWithNode(prefix) != null;
    }

    public TrieNode startWithNode(String prefix) {
        TrieNode preNode = root;
        for (int i = 0; i < prefix.length(); i++) {
            int ch = prefix.charAt(i) - 'a';
            // 查询时无节点返回false;
            if(preNode.next[ch] == null){
                return null;
            }
            preNode = preNode.next[ch];
        }
        return preNode;
    }

    public static void main(String[] args) {
        // ["Trie","insert","startsWith"]
        //[[],["hotdog"],["dog"]]
        Trie trie = new Trie();
        trie.insert("hotdog");
        System.out.println(trie.startsWith("dog"));
    }
}
